package com.jiang.daily.Q3266;

import java.util.PriorityQueue;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/14 18:09
 */
class Solution {
    public int[] getFinalState(int[] nums, int k, int multiplier) {
        if (multiplier == 1 || k == 0) return nums;

        int len = nums.length;
        int mx = 0;
        long m = 1000000007L;
        // 创建一个根据元素值和下标升序的排序队列
        PriorityQueue<long[]> queue = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return Long.compare(a[0], b[0]);
            } else {
                return Long.compare(a[1], b[1]);
            }
        });
        // 将元素加入队列，并找出最大值
        for (int i = 0; i < len; i++) {
            queue.offer(new long[]{nums[i], i});
            mx = Math.max(mx, nums[i]);
        }

        // 如果在k=0之前，取出的元素x满足 × multiplier < mx，无需任何操作
        while(queue.peek()[0] < mx && k > 0) {
            long[] x = queue.poll();
            x[0] *= multiplier;
            queue.offer(x);
            k--;
        }

        // 把队列中的数据放回nums数组， 且如果k != 0, 那么取出的元素y满足 mx × multiplier > y ≥ mx， 操作的次序一定 是从小到大，循环反复。
        for (int i = 0; i < len; i++) {
            long[] x = queue.poll();
            // 当前元素还要 t 次操作
            int t = k / len + (i < k % len ? 1 : 0);
            // 返回原数组
            nums[(int)x[1]] = (int)((x[0] % m) * quickMul(multiplier, t, m) % m);
        }

        return nums;
    }

    /*
    这个代码实现的是快速幂算法，用于计算 (x^y) % m。快速幂算法的时间复杂度是 (O(\log y))，因此对于较大的 (y)，这个算法执行速度会非常快。

    具体来说，这个算法通过将指数 (y) 转换为二进制表示，然后利用二进制表示中的每一位来决定是否需要将当前的基数 (x) 乘到结果中。每次将 (y) 右移一位，相当于将 (y) 除以 2 并取整，同时将当前的基数 (x) 平方并取模 (m)，这样可以减少乘法操作的次数。

    以下是对代码的详细解释：

    初始化结果 res 为 1。
    当 y 大于 0 时，进入循环：
    如果 y 的最低位是 1（即 y & 1 等于 1），则将当前的基数 x 乘到结果 res 中，并取模 m。
    将 y 右移一位（相当于 y = y / 2），即去掉最低位。
    将当前的基数 x 平方并取模 m，即 x = (x * x) % m。
    返回结果 res。
    这个算法在处理大数乘法时非常高效，因为它避免了直接计算大数的幂次，而是通过二进制分解指数来减少计算量。

    例如，计算 (3^{13} \mod 1000) 时，指数 13 的二进制表示是 1101，算法会依次计算 (3^1, 3^2, 3^4, 3^8)，然后根据二进制位来决定是否将相应的幂次乘到结果中。

    因此，这个快速幂算法在处理大数乘法时非常高效，适合用于需要快速计算幂次取模的场景。
     */
    public long quickMul(long x, long y, long m) {
        long res = 1;
        while(y > 0) {
            if ((y & 1) == 1) {
                res = res * x % m;
            }
            y >>= 1;
            x = x * x % m;
        }
        return res;
    }
}
